1. Field of the Invention
Methods and systems consistent with the present invention relate to interleaving, and more particularly, to interleaving depending on readout order decisions.
2. Description of the Related Art
In general, the digital communication systems such as European satellite broadcasting system of the digital video broadcasting standard and U.S.A. terrestrial broadcasting system for High Definition Television (HDTV) randomize, encode, modulate through a modulator, and transmit through transmission cable, MPEG data streams which are synchronized with a transmission clock prior to broadcasting.
Description will be made below in detail on the concept and function of an interleaver.
General communication systems generate random transmission errors occurring sporadically in a random manner, and burst errors clustering at one location.
The burst errors can occur when errors are clustered at one location caused by static electricity from lightening during wireless communications, or when receiving electric power becomes weak on the fading communication lines on which the level of received signal power varies with time.
Since the block codes such Reed-Solomon code can correct only a limited number of bit errors in each code word, correction can be made within the error correction capacity if random errors occur, but block codes are not effective for correcting burst errors.
That is, even though an average bit error rate is reduced because the limited number of bit errors is corrected within each code word by Reed-Solomon coding, an interleaver can improve on the inefficiency of error correcting codes when errors occur in bursts.
Thus, even though burst errors occur on the communication lines when coded data streams are interleaved for randomization of the order and transmitted, a receiver deinterleaves the interleaved data streams to restore the original data streams, changing the burst errors into random errors so that an average error rate can be lowered.
Interleaving randomizes data streams by changing the input and output orders. For example, if data streams are input and stored in the horizontal scan direction on a storage device and the data streams are output in the vertical scan direction, the output data is transmitted in order through communication lines with a bit stream having an interleaving interval of one bit inserted between two input bits.
Hereinafter, description will be made of a conventional interleaving method with reference to the accompanying drawings.
FIG. 1 is a view for showing a structure of data for interleaving.
If 300 data are to be transmitted, for example, the interleaving has to be performed on the 300 data from data number 0 to data number 299. Since the loss of data becomes considerable during transmission if the data are transmitted in the order shown in FIG. 1 as stated above, the interleaving explained with FIG. 2 is performed.
FIG. 2 is a view for showing a data structure obtained when symbol interleaving is applied to the data structure of FIG. 1.
FIG. 2 shows a method storing the data shown in FIG. 1 into three data banks, data bank 0, data bank 1, and data bank 2 denoted by reference numerals 10, 20 and 30, respectively. Data corresponding to the series of data numbers 0 to 299 of FIG. 1 are alternately allocated into the data banks, and sequentially recorded in storage spaces of each data bank as well.
Thus, if three data banks are used for 300 data, each data bank has at least 100 data storage spaces. If the symbol interleaving is performed, the data corresponding to data numbers ‘0, 3, 6, 9, . . . , 297’ are sequentially stored in the storage spaces of the data bank 0 (10), the data corresponding to data numbers ‘1, 4, 7, 10, . . . , 298’ are sequentially stored in the storage spaces of the data bank 1 (20), and the data corresponding to data numbers ‘2, 5, 8, 11, . . . , 299’ are sequentially stored in the storage spaces of the data bank 2 (30).
Next, the data stored in the storage spaces of each of the data banks 1, 2 and 3 (10, 20, and 30) are sequentially read out, and then transmitted.
However, since the symbol interleaving described with FIG. 2 alone cannot fully prevent the data loss during transmissions, an interleaving method as below is additionally proposed.
FIG. 3A is a view for showing a data structure tone-interleaved over the data structure of the data bank 0 (10) shown in FIG. 2, FIG. 3B is a view for showing a data structure tone-interleaved over the data structure of the data bank 1 (20) shown in FIG. 2, and FIG. 3C is a view for showing a data structure tone-interleaved over the data structure of the data bank 2 (30) shown in FIG. 2.
FIGS. 3A, 3B, and 3C are views for showing data structures tone-interleaved over the data structures of the respective data banks shown in FIG. 2. Herein, it is assumed for the tone interleaving that there should be provided as many data storage rows as tone-interleaving processing units (tone-interleaving value L: 10 in FIGS. 3A to 3C) by data bank. The tone interleaving value L can be arbitrarily set to a different value depending on communication environments.
The data banks 10, 20 and 30 have the zero-th data storage rows 10a, 20a, and 30a, the first data storage rows 10b, 20b, and 30b, the second data storage rows 10c, 20c, and 30c, the third data storage rows 10d, 20d, and 30d, the fourth data storage rows 10e, 20e, and 30e, the fifth data storage rows 10f, 20f, and 30f, the sixth data storage rows 10g, 20g, and 30g, the seventh data storage rows 10h, 20h, and 30h, the eighth data storage rows 10i, 20i, and 30i, and the ninth data storage rows 10j, 20j, and 30j. 
In FIG. 3A, the data sequentially stored in the storage spaces of the data bank 0 (10) shown in FIG. 2 are sequentially and alternately stored into the data storage rows 10a, 10b, 10c, 10d, 10e, 10f, 10g, 10h, 10i, 10j. 
Further, the data sequentially stored in the storage spaces of the data bank 0 (10) shown in FIG. 2 are sequentially stored in the storage spaces of the individual data storage rows 10a, 10b, 10c, 10d, 10e, 10f, 10g, 10h, 10i, and 10j. 
The tone interleaving according to the above principle is applied in the same manner to FIG. 3B and FIG. 3C. The data interleaved in FIG. 2, FIG. 3A, FIG. 3B, and FIG. 3C are first sent sequentially in order from the zero-th data storage row 10a of the data bank 0 (10) to the ninth data storage row 10j, sequentially sent in order from the zero-th data storage row 20a of the data bank 20 to the ninth data storage row 20j and, sequentially sent in order from the zero-th data storage row 30a of the data bank 2 (30) to the ninth data storage row 30j. 
If the symbol interleaving and the tone interleaving are used for data transmissions, the possibility of damage to data becomes lower than when only the symbol interleaving is used. However, another additional interleaving is proposed for the integrity of data transfer.
FIGS. 4A, 4B, and 4C are views for showing a data structure with cyclic-interleaving-performed over the data structure of each data bank shown in FIGS. 3A, 3B and 3C.
Here, dividing the whole data set into three arrays such as arrays A, B, and C in reading out data of the respective data banks 10, 20 and 30 in FIGS. 3A, 3B, and 3C, the cyclic-interleaving refers to shifting the arrays of each data bank. Further, the number of data of an array in which array shifting occurs is referred to as a cyclic interleaving value Q. The cyclic interleaving value Q can be arbitrarily set to a different value depending on communication environments.
In FIGS. 4A, 4B, and 4C, the data structure of each of data bank 10, 20, and 30 are first divided into three arrays. The first array A is formed with 33 data consecutively read out, and the second array B is formed with 33 data consecutively read out as well. The third array C is formed with 34 data consecutively read out.
The cyclic interleaving in FIG. 4A indicates data readout when array shifting is not carried out. The number of data of the array in which the shifting occurs is ‘0’ so that the cyclic interleaving value becomes ‘0’. Therefore, the data readout from the data bank 0 (10) is carried out in order of the array A, array B, and array C.
The cyclic interleaving in FIG. 4B indicates the data readout in a state where array shifting is carried out over the array A, and the number of data of the array in which the shifting occurs is ‘33’ so that the cyclic interleaving value Q becomes ‘33’. Thus, the data readout from the data bank 1 (20) is carried out in order of the array A, array B, and array C.
The cyclic interleaving in FIG. 4C indicates the data readout in a state where array shifting is carried out over the arrays A and B, and the number of data of the array in which the shifting occurs is ‘66’ so that the cyclic interleaving value Q becomes ‘66’. Thus, the data readout from the data bank 1 (20) is carried out in order of the array B, array C, and array A.
If the cyclic interleaving described with FIGS. 4A, 4B, and 4C is used, the data loss rate can be reduced upon data transmissions.
However, there exist problems in that the additional cyclic interleaving described as above generally requires additional memories in which the data structure cyclic-interleaved over each of the data banks 10, 20, and 30 is stored and the processing speed is lowered in such circumstances.